package club.xiaojiawei.back;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/22/22 6:59 PM
 * @question 52. N皇后 II
 * @description n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
 */
public class TotalNQueens52 {

    public static void main(String[] args) {
        TotalNQueens52 test = new TotalNQueens52();
        int result = test.totalNQueens2(9);
        System.out.println(result);
    }

    /**
     * 递归回溯
     * @param n
     * @return
     */
    public int totalNQueens(int n) {
        postion = new int[n];
        reversion(0, n);
        return count;
    }

    int[] postion;

    int count;

    public void reversion(int row, int n){
        if (row == n){
            count++;
        }
        for (int i = 0; i < n; i++) {
            if (judge(row, i)){
                postion[row] = i;
                reversion(row + 1, n);
            }
        }
    }

    public boolean judge(int row, int col){
        for (int i = 0; i < row; i++){
            if (postion[i] == col || Math.abs(col - postion[i]) == Math.abs(row - i)){
                return false;
            }
        }
        return true;
    }

    /**
     * 二进制递归回溯
     * @param n
     * @return
     */
    public int totalNQueens2(int n) {
        reversion2(0, 0, 0, 0, n);
        return count;
    }

    public void reversion2(int row, int l, int m, int r, int n){
        if (row == n){
            count++;
            return;
        }
        int temp = ((1 << n) - 1) & (~(l | m | r));
        int num = Integer.bitCount(temp);
        for (int j = 0; j < num; j++) {
            int i = temp & ((~temp) + 1);
            temp ^= i;
            reversion2(row + 1, (l | i) << 1, m | i, (r | i) >> 1, n);
        }
    }
}
